"""
21. 合并两个有序链表
简单
相关标签
premium lock icon
相关企业
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。



示例 1：


输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]


提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列


"""
from typing import Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists_Y1(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        pass
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val<list2.val:
            head = ListNode(list1.val)
            list1 = list1.next
        else:
            head = ListNode(list2.val)
            list2 = list2.next
        cur = head
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = ListNode(list1.val)
                list1 = list1.next
            else:
                cur.next = ListNode(list2.val)
                list2 = list2.next
            cur = cur.next
        if list1:
            cur.next = list1
        else:
            cur.next = list2
        return head

    def mergeTwoLists_res1(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dum = ListNode(0)
        while list1 and list2:
            if list1.val < list2.val:
                cur.next, list1 = list1, list1.next
            else:
                cur.next, list2 = list2, list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dum.next




if __name__ == '__main__':
    # 创建测试用例的辅助函数
    def create_linked_list(arr):
        """根据数组创建链表"""
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for i in range(1, len(arr)):
            current.next = ListNode(arr[i])
            current = current.next
        return head


    def print_linked_list(head):
        """打印链表"""
        result = []
        current = head
        while current:
            result.append(current.val)
            current = current.next
        return result


    # 测试用例 1
    # 输入：l1 = [1,2,4], l2 = [1,3,4]
    # 输出：[1,1,2,3,4,4]
    list1_1 = create_linked_list([1, 2, 4])
    list2_1 = create_linked_list([1, 3, 4])
    solution = Solution()
    result1 = solution.mergeTwoLists(list1_1, list2_1)
    print(f"测试用例 1: {print_linked_list(result1)}")

    # # 测试用例 2
    # # 输入：l1 = [], l2 = []
    # # 输出：[]
    # list1_2 = create_linked_list([])
    # list2_2 = create_linked_list([])
    # result2 = solution.mergeTwoLists(list1_2, list2_2)
    # print(f"测试用例 2: {print_linked_list(result2)}")
    #
    # # 测试用例 3
    # # 输入：l1 = [], l2 = [0]
    # # 输出：[0]
    # list1_3 = create_linked_list([])
    # list2_3 = create_linked_list([0])
    # result3 = solution.mergeTwoLists(list1_3, list2_3)
    # print(f"测试用例 3: {print_linked_list(result3)}")
    #
    # # 测试用例 4
    # # 输入：l1 = [1,2,3], l2 = [4,5,6]
    # # 输出：[1,2,3,4,5,6]
    # list1_4 = create_linked_list([1, 2, 3])
    # list2_4 = create_linked_list([4, 5, 6])
    # result4 = solution.mergeTwoLists(list1_4, list2_4)
    # print(f"测试用例 4: {print_linked_list(result4)}")
    #
    # # 测试用例 5
    # # 输入：l1 = [-1,0,1], l2 = [-2,3,4]
    # # 输出：[-2,-1,0,1,3,4]
    # list1_5 = create_linked_list([-1, 0, 1])
    # list2_5 = create_linked_list([-2, 3, 4])
    # result5 = solution.mergeTwoLists(list1_5, list2_5)
    # print(f"测试用例 5: {print_linked_list(result5)}")


